1. Field of the Invention
The invention relates to computer-based systems that scan hand-drawn drawings into a computer and process them. More particularly, it relates to systems that scan hand-drawn cartoon animation and prepare the scanned drawings for computer-performed processing, including inking, painting, and camera tasks.
2. Background
The traditional manual process for preparing cartoon animation begins with hand-drawn animation, typically pencil on paper. The drawings then go through a three-step process before they appear on film.
The first step is xe2x80x9cinkxe2x80x9d. The lines of the pencil drawings are traced onto the front of clear plastic acetate sheets (called cels) with one or more colors of ink. If a completely black line is acceptable, the drawings are often photocopied onto the cel. In either case, the result is a solid, opaque line.
The second step is xe2x80x9cpaintxe2x80x9d. After the front of the cel is inked, the drawing is filled in on the back of the cel with various colors of paint.
The third step is xe2x80x9ccameraxe2x80x9d. All the painted cels for a particular frame are stacked and photographed to generate the final frame.
This traditional, three-step, manual process of inking and painting cels has a number of drawbacks. It is very labor intensive. It is difficult to avoid painting errors, such as painting a region the wrong color on one cel, and painting errors are time consuming to fix. It is very labor intensive to make a widespread color change. The cels are not completely transparent, so colors on lower cels in a final frame appear darker and desaturated. And a cel will get dusty and dirty, and that dirt appears visually in the final frame if the cel is not cleaned each time it is used.
In recent years, several computer-based systems have been developed to address the drawbacks of the manual ink-and-paint process. One such system is the USAnimation System, available from USAnimation, Inc. of Hollywood, Calif. Generally, such systems scan the original pencil drawings into the computer, and then perform the ink, paint, and camera tasks on the computer. The USAnimation product reduces the line art to vectors representing the center of the line art. These vectorsxe2x80x94the xe2x80x9ccolor artxe2x80x9dxe2x80x94are found by pixel operations, using three separate copies of the image pixmap. With a drawing on standard 16 by 12 inch paper scanned at 300 dots per inch, the size of each pixmap exceeds 17 million bits. The line art polygons are then formed as a set of vector polygons, each polygon being formed around one unbroken, branchless section of the color art. The result of this process is illustrated in FIG. 1A, which shows a drawn xe2x80x9cYxe2x80x9d digitized into a bitmap, and FIG. 1B, which shows the three regions of line art 102, 104, and 106 created by the USAnimation product from the bitmap of FIG. 1A.
Many such systems scan the pencil drawing as a pixmap with various levels of gray, so the scanned line has a soft edge. A xe2x80x9cpixmapxe2x80x9d is a data structure storing an image in pixel representation. A pixel is a picture element; if one thinks of a picture as a raster of points, a pixel is a point. In a pixmap, a pixel will have one or more bits of information, the number of bits being referred to as the xe2x80x9cdepthxe2x80x9d, which bits may represent gray scale or color information.
Generally, the lines of the pencil drawing in the pixmap are recolored to reflect the required ink color, and the appropriate regions of the pixmap are painted. Then, these digital cels are layered in the computer through a digital compositing process and written to an appropriate medium, such as video tape or film.
Such a digital process has a number of advantages over the manual process. It is less labor-intensive because computer paint programs allow for greater productivity than processes using physical ink and paint. Fixing paint errors on a computer is quick and easy. Widespread color changes in ink or paint can be implemented with minimal labor. Digital cels are completely transparent, so there are no problems with color shifts, and therefore no inherent limit in the complexity of the cartoon. Dirt specks picked up in the scanning process are easily eliminated from the digital cels and never reappear.
However, in such systems, a new set of issues arises and some old problems still exist.
First, the resolution of the pixmap is determined at scanning time. In order to avoid digital artifacts, it is necessary that the scanning resolution for a cel be as large, or larger than the output resolution multiplied by the most extreme truck (or amount of zoom in) for that cel.
Second, the effort and computer resources required to ink and to paint increase with the scanning resolution.
Third, painting errors are still difficult to prevent and detect. The pixmap for a digital cel is relatively large, requiring a significant amount of computers memory in the paint program. If there is not enough memory available to store more than a few cels at a time in the paint program""s memory, it may be difficult to see the cartoon animate in order to detect painting errors.
And fourth, the ink may retain the variable density of the original pencil line in subsequent digital processing, a departure from the look of traditional animation.
In general, in one aspect, the invention provides a computer-implemented method for converting a pixmap representing a drawing into a set of vectors representing the drawing. The method includes forming or tracing closed loops of points or vectors around boundaries between edge and non-edge pixels in the pixmap; identifying each loop as defining an outer perimeter or as defining a hole associated with some particular outer perimeter; and for each outer perimeter, identifying as an ink art region an area defined by an outer perimeter minus any areas defined by any holes associated with the outer perimeter. In another aspect, then method includes creating a color art graph of vectors within an ink art region, the color art graph extending substantially to all extrema of the ink art region and separately enclosing all holes within the ink art region. In another aspect, the method includes creating a central ink art region at the join of a xe2x80x9cYxe2x80x9d shape where a part of an ink art region forms such a shape. In another aspect, the central ink art region is formed by calculating the Delaunay triangulation of points defining the boundary of the ink art region and then defining the central ink art region as corresponding to a Delaunay triangle all of whose sides are interior to the original ink art region. In another aspect, the method includes closing gaps between dangling ends of the color art graph. In another aspect, the method includes extending a dangling end of the color art graph to join a nearby section of the same or a different color art graph. In another aspect, the method includes distinguishing loops by their clockwise or counterclockwise orientation. In another aspect, the method includes distinguishing loops by the signs of their areas.
In another aspect, the method includes creating a color art graph by creating a set of interior vectors and taking a non-end point of each interior vector as an end point to a color art vector within an ink art region. In another aspect, the method includes creating a pixmap by scanning a drawing into a computer with an optical scanner to obtain a scanned raster of pixels representing the drawing. In another aspect, the method includes removing pixels.
In another aspect, the method includes smoothing a closed loop and, in another aspect, doing the smoothing by moving end points of closed loop vectors toward a weighted average of their positions and their neighboring points"" position. In another aspect, the method includes means for filtering vectors by replacing sequential and approximately colinear vectors with a resultant vector.
In another aspect, the method includes smoothing a color art graph, including, in another aspect, smoothing by moving points of color art vectors toward a weighted average of their positions and their neighboring points positions. In another aspect, the vectors of the closed loops are straight line segments. In another aspect, the color art vectors are straight line segments.
In another aspect, the method includes creating closed loops by considering the pixels of the image in a scan order, the present pixel in the scan order being called the scan pixel, and for each scan pixel performing the following steps: if the scan pixel is not an edge pixel, advancing to the next pixel in the scan order as the scan pixel and repeating this edge-pixel test, or if the scan order is exhausted, terminating;the process of creating closed loops; taking the scan pixel as the current pixel and beginning a stroke; finding the direction of the counterclockwise-most white neighbor of the current pixel beginning from an initial direction; selecting as the edge direction the direction resulting from one step counterclockwise from the direction found in the preceding steps; marking the current pixel as not being an edge and ask being visited in general; marking the current pixel as visited from the edge direction; turning the edge direction one step clockwise; if the neighbor pixel and the edge direction is white, adding a vector connecting the current pixel and the white neighbor pixel to the tail end of the stoke, or if the neighbor pixel in the edge direction is not an edge pixel and has not been marked as visited, or if the neighbor pixel in the edge direction has not been marked as visited, making the neighbor pixel the current pixel and turning the edge direction 180xc2x0, and in all three cases looping back to the step of marking the current pixel as not an edge pixel and as visited in general; connecting the ends of the stroke to form a closed loop; and adding the closed loop to the end of a loop list.
In another aspect, the method includes the following steps for building an ink art region: picking the first (or next) loop in the loop list as the current list; computing the signed area defined by the current loop and, if the area is positive, adding the current loop to the tail end of an ink art list as an ink art region, or otherwise, marking the current loop as a hole and searching the ink art list from its beginning for the first ink art region that contains any point of the current loop and adding the current loop of the hole to the found, first ink art region.
In general, in another aspect, the invention provides a system for converting a drawing represented in a pixmap of pixels into a vector representation of the drawing. The system includes means for forming closed loops of edge vectors following the boundaries between edge pixels and non-edge pixels; means for building ink art regions from loops so that each ink art region is a continuous region enclosed by edge vectors; means for finding nearest neighbors among a set of boundary points of the ink art regions and linking them with link segments; and means for identifying those link segments between nearest neighbors that pass through the interior of one of the ink art regions (which link segments are designated interior links). In another aspect, the system includes means for creating a color art graph by tracing a connection from an interior point of one interior link of an ink art region to its neighboring interior links or the same ink art region to define a color art vector of the color art graph. In another aspect, the system includes means for removing dirt pixels.
In another aspect, the system includes means for filtering superfluous boundary points from the boundary of ink art regions or superfluous points from color art graphs; means for extending a color art graph to close gaps between dangling ends; means for extending a color art graph to join at dangling ends to a nearby section of the same or different color art graph; means for removing registration holes from the pixmap; and means for translating, resizing, and rotating color art graphs and ink art regions.
In another aspect, the method and system include using midpoints of link segments joining inside and outside boundary points as points defining color art vectors.
In general, in another aspect, the invention features a method for converting a pixmap representing a drawing into a geometric point-based representation of the drawing by means of the features recited above. In another aspect, the method includes calculating nearest-neighbor vectors joining nearest-neighbors among those points that At define an ink art region; identifying those nearest-neighbor vectors that lie interior of the ink art region; and identifying as a location to break the line art region the location of an interior nearest-neighbor vector that has, at each end of itself, a nearest-neighbor vector connected to itself and lying on the same side of itself. In another aspect, the method includes distinguishing at least two colors of non-white pixels (with may be called red and black) and, after they are used in creating color art graphs, distinguishing any closed loops formed by tracing red pixels from any closed loops formed by tracing black pixels.
The invention has a number of advantages.
For example, the vector representation is resolution independent. This means that it can be scaled to virtually arbitrary size without the appearance of digital artifacts. When the input to an ink and paint process is such a vector representation, the final output resolution does not have to be predetermined.
Also, because of the resolution independence, the speed of inking and painting is largely independent of the output resolution.
Also, the vector representation is more compact than an equivalent pixmap representation. This allows a paint application employing the invention to load dozens of cels simultaneously and flip through them fast enough to allow viewing of the animation. This allows the operator to prevent nearly all errors in the ink and paint stages of production.
Also, the vector representation provides an accurate duplication of the opaque qualities of a traditional, hand-inked line.
Also, the nuances of the artist""s original pencil line may be replicated and preserved, with the same (or better) quality than would be produced by a traditional hand-inker or by a photocopy machine. This includes a great deal of detail, such as the variable thickness of lines.
Also, two vector representations of the drawing are produced, one for the ink (line art) and one for the paint (color art). The color art vectors describe regions for paint that extend underneath the bounding line art. Also, by first creating a line art vector representation, and then color art vectors from the line art vectors, the amount of time a large pixmap must be kept in program memory is reduced.
Also, vector ink is broken at natural locations for color changes, such as the joints between lines. This helps to automate the process of inking, because the operator does not have to manually specify all the boundaries between ink colors.
Also, complex drawings in the invention do not lead to serious performance degradation.
Also, the invention is robust in the sense that it can handle a wide range of input cases, and the output accurately reflects the input image with little or no manual intervention.
Also, the vectors may be used to resize and/or rotate a pixmap with little loss of quality. The pixmap is vectorized and the vector representation is resized and/or rotated and then converted back to a pixmap by rendering the vector polygons, optionally with anti-aliasing.
Also, the vector representation may be used to improve the quality of the image by anti-aliasing, by taking the vectorized pix map and converting it back to an image pixmap by rendering the vector polygons with anti-aliasing. Also, the vector representation may be used for the purpose of compression of data.
Also, the vector representation may be used for image comparison and matching of corresponding parts of similar images. By geometric analysis of the vector representation of an image, comparison of two or more images to identify a corresponding part of successive images is performed and corresponding regions may be identified to be painted automatically.